The present invention relates to an image search apparatus and method for searching for an image.
Conventionally, various techniques for searching for a similar image have been proposed. Similar image search techniques for a natural image, which have nearly reached a practical level, often use color information as an image feature amount. Most of techniques compute a histogram that pertains to color information and conduct a search using the RGB ratio or a combination of colors that frequently appear in an image.
However, in the conventional technique, since the position information of color is lost, search precision is not always high. For example, Japanese Laid-Open Patent No. 8-249349 discloses pattern matching using feature amounts (representative colors) of a plurality of blocks obtained by segmenting an image. However, in this technique, the distance between the feature amounts of two image blocks to be matched must be computed, resulting in a huge computation volume. When a representative color is used as a feature amount, three, i.e., R, G, and B data must be processed, thus further complicating computations. Also, since comparison is made using the feature amount itself, high comparison precision can be obtained but a similar image cannot be obtained by a search even due to a change in angle of an image or a change in position of an object. In other words, a so-called robust similar image search that appropriately obtains an image by a search with some ambiguity that can absorb a change in image angle or object position, some image feature amount difference depending on image sensing conditions, and the like, cannot be made.
Therefore, in order to search natural images, it is a common practice to assign keywords to images, and to perform an image search using the keywords. However, this keyword assignment requires much labor. Furthermore, images which have no keywords must be presented as thumbnail images and must be selected manually, thus complicating search operation.
As described above, a similar image search system, which searches natural images and has nearly reached a practical level, uses color information as an image feature amount. Most of such systems compute the RGB ratio or combinations of colors that frequently appear in an image by computing a histogram (to be referred to as a color histogram hereinafter) that pertains to color information, and conduct a search using them as feature amounts. In such search process, it is a common practice to make an inner product computation of the color histogram as comparison means.
However, the volume of inner product computation of the color histogram increases in proportion to the number of registered images, and when a large number of images have been registered, a long search process time is required.
Irrespective of the search technique used, the search time normally increases as the number of registered images increases. Especially, in the aforementioned similar image search, one-to-one comparison must be made between a query image as an example image and a large number of registered images to determine similarities. For this reason, the number of images to be compared (i.e., the number of registered images) has a large influence on the search time.
The present invention has been made in consideration of the above problems, and has as its object to narrow down images that must undergo similarity computations with a query image to fewer images at high speed, and implement a high-speed similar image search.
It is another object of the present invention to attain a high-speed similar image search that takes the layout of image feature amounts into consideration.
It is still another object of the present invention to attain a similar image search that can search for a similar image in consideration of the layout of image feature amounts and can absorb differences due to variations of image sensing conditions and the like.
It is still another object of the present invention to achieve a quick similar image search by reducing the similarity computation volume by computing similarity between images in such a manner that a feature amount group is expressed by a single label, and an image is expressed by a label sequence or matrix.
It is still another object of the present invention to greatly improve the processing speed of an image search process using labels by appropriately managing a label sequence or matrix.
It is still another object of the present invention to attain a more effective similar image search using a method that permits certain ambiguity as to label position such as DP matching, fuzzy nondeterministic automaton, or the like upon determining similarity between a query image and an image to be compared by comparing label sequences or matrices.
It is still another object of the present invention to provide an image search apparatus or method which can attain a high-speed image search (or narrowing down) prior to or in place of an inner product computation of a color histogram.
It is still another object of the present invention to reduce the number of images to a value that the system can process by making a high-speed presearch using an index file.
It is still another object of the present invention to allow narrowing down in consideration of the ambiguity level of a search designated by the user.